Compute researcher’s H-index of citations [Counting Sort]

Time: O(N); Space: O(N); medium

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s H-index.

According to the definition of h-index on Wikipedia: “A scientist has index H if H of his/her N papers have at least H citations each, and the other N h papers have no more than H citations each.”

Example 1:

Input: citations = [3, 0, 6, 1, 5]

Output: 5

Explanation:

  • It means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.

  • Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his H-index is 3.

1. Counting sort

[5]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(N)
    """
    def hIndex(self, citations) -> int:
        """
        :type citations: List[int]
        :rtype: int
        """
        n = len(citations)
        count = [0] * (n + 1)

        for x in citations:
            # Put all x >= n in the same bucket
            if x >= n:
                count[n] += 1
            else:
                count[x] += 1

        h = 0
        for i in reversed(range(0, n + 1)):
            h += count[i]
            if h >= i:
                return i

        return h

[6]:

s = Solution1()
citations = [3, 0, 6, 1, 5]
assert s.hIndex(citations) == 3

[7]:

class Solution2(object):
    """
    Time: O(NlogN)
    Space: O(1)
    """
    def hIndex(self, citations) -> int:
        """
        :type citations: List[int]
        :rtype: int
        """
        citations.sort(reverse=True)

        h = 0
        for x in citations:
            if x >= h + 1:
                h += 1
            else:
                break
        return h

[8]:

s = Solution2()
citations = [3, 0, 6, 1, 5]
assert s.hIndex(citations) == 3

[9]:

class Solution3(object):
    """
    Time: O(NlogN)
    Space: O(N)
    """
    def hIndex(self, citations) -> int:
        """
        :type citations: List[int]
        :rtype: int

        """
        return sum(x >= i + 1 for i, x in enumerate(sorted(citations, reverse=True)))

[10]:

s = Solution3()
citations = [3, 0, 6, 1, 5]
assert s.hIndex(citations) == 3